package com.zxy.leetcode.test;

import java.util.Arrays;

/**
 * 三色旗
 *
 * 假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，
 * 您希望将之分类，并排列为蓝、白、红的顺序，注意您只能在绳子上进行调换动作，
 * 而且一次只能调换两个旗子。蓝、白、红分别用1、2、3表示，
 * 比如输入是[1,2,3,1,2,3,1,2,3]，排序完结果为[1,1,1,2,2,2,3,3,3]。
 * 空间复杂度要求O(1)，时间复杂度要求O(n)。
 *
 * 测试用例：
 * 1,2,3,1,2,3,1,2,3
 * 3,2,1,3,2,1,3,2,1
 * 1,2,1,2,3,1,3,1,3,2,3,1,2,3,1,3,2,2,2,3,1,1
 *
 */
public class ThreeColorRope {

    public static void main(String[] args) {
        int[] nums1 = {1,2,3,1,2,3,1,2,3};
        sort(nums1);
        System.out.println(Arrays.toString(nums1));

        int[] nums2 = {3,2,1,3,2,1,3,2,1};
        sort(nums2);
        System.out.println(Arrays.toString(nums2));

        int[] nums3 = {1,2,1,2,3,1,3,1,3,2,3,1,2,3,1,3,2,2,2,3,1,1};
        sort(nums3);
        System.out.println(Arrays.toString(nums3));
    }

    /*
    思路：2一定是放中间的，先不管2，
    碰到1放到最左边，碰到3放到最右边
     */
    private static void sort(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int i = 0;

        while (i <= right) {
            if (nums[i] == 2) {
                i ++;
            }else if (nums[i] == 1) {
                // 跟前面的数字互换，前面的数字只能1或2
                swap(nums, left, i);
                left ++;
                i ++;
            }else if (nums[i] == 3) {
                while (i < right && nums[right] == 3) {
                    right --;
                }
                // 跟后面的换，但后面的可能是1或2，被换的数字位置可能不正确，还需要再进行比较，所以i不累加
                swap(nums, i, right);
                right --;
            }else {
                // ignore
            }
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int a = nums[i];
        nums[i] = nums[j];
        nums[j] = a;
    }

}
